import java.util.LinkedList;

public class bfs {

	public static LinkedList<Node> findPath(Graphe graphe, int s, int t) {
		LinkedList<Node> path = new LinkedList<Node>();
		if (s == t) {
			path.addFirst(graphe.nodesInt.get(s));
			return path;
		}
		if (s > graphe.size || t > graphe.size) {
			return path;
		}

		int n = graphe.size + 1;
		boolean[] visited = new boolean[n];
		int[] previous = new int[n];
		int cId = t;
		for (int i = 1; i < n; i++) {
			visited[i] = false;
			previous[i] = -1;
		}
		Node source = graphe.nodesInt.get(s);
		Node current = source; 
		Node destination = graphe.nodesInt.get(t);
		LinkedList<Node> queue = new LinkedList<Node>();
		queue.add(source);
		while (current.ID != destination.ID) {
			current = queue.remove();
			for (Node toAdd : current.voisins) {
				if (!visited[toAdd.ID]) {
					visited[toAdd.ID] = true;
					previous[toAdd.ID] = current.ID;
					queue.add(toAdd);

				}
			}

		}
		path.addFirst(destination);
		while (cId != s) {
			cId = previous[cId];
			path.addFirst(graphe.nodesInt.get(cId));
		}

		return path;
	}

}
